package offer.day22;

public class No37Deserialize {
    /*
     * 面试题37：序列化二叉树
     * 题目：请实现两个函数，分别用来序列化和反序列化二叉树
     *
     * 序列化：一棵二叉树按照某种遍历方式的结果一某种格式保存为字符串，从而可使内存中建立起来的二叉树持久保存
     * 反序列化：根据某种遍历顺序得到的序列化字符串结果，重新构建（重构）二叉树
     *
     * 思路：
     * 序列化：通过先序遍历二叉树的方式进行序列化
     * 反序列化  根据序列化的结果进行反序列化，重构二叉树
     * 			对其进行分割使用split,然后使用一个全局常量index定位索引的节点
     * 			若不为空，（表示节点不是$）创建创新的二叉树结点，将其存入（根节点存入）
     * 					然后根据先序遍历的思想---根左右节点进行遍历
     * 					再判断其左节点和右节点        继续 若不为空就将其创建新节点。。. 重复上边步骤
     *			若为空,则直接返回node(初始值定为null)
     * */
    public static void main(String[] args) {
        No37Deserialize d = new No37Deserialize();

        BinaryTreeNode root = new BinaryTreeNode(8);
        BinaryTreeNode one = new BinaryTreeNode(8);
        BinaryTreeNode two = new BinaryTreeNode(7);
        BinaryTreeNode three = new BinaryTreeNode(9);
        BinaryTreeNode four = new BinaryTreeNode(2);
        BinaryTreeNode five = new BinaryTreeNode(4);
        BinaryTreeNode six = new BinaryTreeNode(7);

        root.left = one;
        root.right = two;
        one.left = three;
        one.right = four;
        two.left = null;
        two.right = null;
        three.left = null;
        three.right = null;
        four.left = five;
        four.right = six;
        five.left = null;
        five.right = null;
        six.left = null;
        six.right = null;

        String s = new String();
        //序列化二叉树
        s = d.Serialize(root);
        System.out.println("用先序遍历的方式序列化二叉树，输出序列结果：" + s);
        //反序列化二叉树
        BinaryTreeNode new_root = d.Deserialize(s);
        System.out.println("反序列化二叉树后，以先序遍历的方式输出二叉树：");
        if (new_root != null) {
            PrintBinaryTree(new_root);
        }
    }

    private String Serialize(BinaryTreeNode root) {
        StringBuilder sb = new StringBuilder();
        if (root == null) {
            sb.append("$,");
            return sb.toString();
        }
        sb.append(root.val + ",");
        sb.append(Serialize(root.left));
        sb.append(Serialize(root.right));
        return sb.toString();
    }

    private BinaryTreeNode Deserialize(String s) {
        int length=s.length();
        String[] str=s.split(",");
        return DeserializeNode(str,length);

    }

    int index=-1;
    private BinaryTreeNode DeserializeNode(String[] str, int length) {
        index++;
        BinaryTreeNode node=null;
        if(index>=length) return null;
        if(!str[index].equals("$")){
            node=new BinaryTreeNode(Integer.valueOf(str[index]));
            node.left=DeserializeNode(str,length);
            node.right=DeserializeNode(str,length);
        }
        return node;
    }

    private static void PrintBinaryTree(BinaryTreeNode root) {
        if (root == null) return;
        System.out.print(root.val+",");
        if (root.left != null) {
            PrintBinaryTree(root.left);
        }
        if (root.right != null) {
            PrintBinaryTree(root.right);
        }
    }


}
